/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package batailledesardennes.util.geomFloat;

import batailledesardennes.util.FastMath;
import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.CoordinateSequence;
import com.vividsolutions.jts.geom.Geometry;
import com.vividsolutions.jts.geom.GeometryCollection;
import com.vividsolutions.jts.geom.GeometryFactory;
import com.vividsolutions.jts.geom.LineString;
import com.vividsolutions.jts.geom.LinearRing;
import com.vividsolutions.jts.geom.MultiPolygon;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *
 * @author charly
 */
public class GeomUtils {

    public static Point getLinesIntersection(Point p1, Point p2, Point p3, Point p4) {
        return getLinesIntersection(p1.getX(), p1.getY(), p2.getX(), p2.getY(),
                p3.getX(), p3.getY(), p4.getX(), p4.getY());
    }

    public static Point getLinesIntersection(float x1, float y1, float x2, float y2,
            float x3, float y3, float x4, float y4) {
        float det1And2 = det(x1, y1, x2, y2);
        float det3And4 = det(x3, y3, x4, y4);
        float x1LessX2 = x1 - x2;
        float y1LessY2 = y1 - y2;
        float x3LessX4 = x3 - x4;
        float y3LessY4 = y3 - y4;
        float det1Less2And3Less4 = det(x1LessX2, y1LessY2, x3LessX4, y3LessY4);
        if (det1Less2And3Less4 == 0) {
            // the denominator is zero so the lines are parallel and there's either no solution (or multiple solutions if the lines overlap) so return null.
            return null;
        }
        float x = (det(det1And2, x1LessX2,
                det3And4, x3LessX4)
                / det1Less2And3Less4);
        float y = (det(det1And2, y1LessY2,
                det3And4, y3LessY4)
                / det1Less2And3Less4);
        return new Point(x, y);
    }

    public static boolean linesIntersect(float x1, float y1, float x2, float y2,
            float x3, float y3, float x4, float y4) {
        return getLinesIntersection(x1, y1, x2, y2, x3, y3, x4, y4) != null;
    }

    public static boolean linesIntersect(Point p1, Point p2, Point p3, Point p4) {
        return linesIntersect(p1.getX(), p1.getY(), p2.getX(), p2.getY(),
                p3.getX(), p3.getY(), p4.getX(), p4.getY());
    }

    public static boolean linesSegmentsIntersect(float x1, float y1, float x2, float y2,
            float x3, float y3, float x4, float y4) {
        // Return false if either of the lines have zero length
        if ((x1 == x2 && y1 == y2)
                || (x3 == x4 && y3 == y4)) {
            return false;
        }
        // Fastest method, based on Franklin Antonio's "Faster Line Segment Intersection" topic "in Graphics Gems III" book (http://www.graphicsgems.org/)
        float ax = x2 - x1;
        float ay = y2 - y1;
        float bx = x3 - x4;
        float by = y3 - y4;
        float cx = x1 - x3;
        float cy = y1 - y3;

        float alphaNumerator = by * cx - bx * cy;
        float commonDenominator = ay * bx - ax * by;
        if (commonDenominator > 0) {
            if (alphaNumerator < 0 || alphaNumerator > commonDenominator) {
                return false;
            }
        } else if (commonDenominator < 0) {
            if (alphaNumerator > 0 || alphaNumerator < commonDenominator) {
                return false;
            }
        }
        float betaNumerator = ax * cy - ay * cx;
        if (commonDenominator > 0) {
            if (betaNumerator < 0 || betaNumerator > commonDenominator) {
                return false;
            }
        } else if (commonDenominator < 0) {
            if (betaNumerator > 0 || betaNumerator < commonDenominator) {
                return false;
            }
        }
        // if commonDenominator == 0 then the lines are parallel.
        if (commonDenominator == 0) {
            // This code wasn't in Franklin Antonio's method. It was added by Keith Woodward.
            // The lines are parallel.
            // Check if they're collinear.
            float collinearityTestForP3 = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2);	// see http://mathworld.wolfram.com/Collinear.html
            // If p3 is collinear with p1 and p2 then p4 will also be collinear, since p1-p2 is parallel with p3-p4
            if (collinearityTestForP3 == 0) {
                // The lines are collinear. Now check if they overlap.
                if (x1 >= x3 && x1 <= x4 || x1 <= x3 && x1 >= x4
                        || x2 >= x3 && x2 <= x4 || x2 <= x3 && x2 >= x4
                        || x3 >= x1 && x3 <= x2 || x3 <= x1 && x3 >= x2) {
                    if (y1 >= y3 && y1 <= y4 || y1 <= y3 && y1 >= y4
                            || y2 >= y3 && y2 <= y4 || y2 <= y3 && y2 >= y4
                            || y3 >= y1 && y3 <= y2 || y3 <= y1 && y3 >= y2) {
                        return true;
                    }
                }
            }
            return false;
        }
        return true;
    }
    
    public static boolean linesSegmentsIntersect(Point p1, Point p2, Point p3, Point p4) {
        return linesSegmentsIntersect(p1.getX(), p1.getY(), p2.getX(), p2.getY(), p3.getX(), p3.getY(), p4.getX(), p4.getY());
    }

    public static float det(float a, float b, float c, float d) {
        return a * d - b * c;
    }

    public static float distance(float x1, float y1, float x2, float y2) {
        return FastMath.sqrt(distanceSq(x1, y1, x2, y2));
    }

    public static float distanceSq(float x1, float y1, float x2, float y2) {
        x1 -= x2;
        y1 -= y2;
        return x1 * x1 + y1 * y1;
    }

    public static boolean collinear(float x1, float y1, float x2, float y2, float x3, float y3) {
        float test = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2);
        return test == 0;
    }

    public static int ccw(float x1, float y1,
            float x2, float y2) {
        return FastMath.counterClockwise(0, 0, x1, y1, x2, y2);
    }

    public static int ccw(Point p0, Point p1, Point p2) {
        return FastMath.counterClockwise(p0.getX(), p0.getY(), p1.getX(), p1.getY(), p2.getX(), p2.getY());
    }

    /**
     * Returns angle from pt 0 to pt1 in range -PI included ;PI excluded
     * @param x0
     * @param y0
     * @param x1
     * @param y1
     * @return
     */
    public static float findSignedAngle(float x0, float y0, float x1, float y1) {
        float x = x1 - x0;
        float y = y1 - y0;
        float angle = FastMath.atan2(y, x);
        return angle;
    }

    /**
     * Returns angle diff from pt 0 to pt1 and pt0 to pt2
     * @param x0
     * @param y0
     * @param x1
     * @param y1
     * @param x2
     * @param y2
     * @return
     */
    public static float findSignedAngleRelative(float x0, float y0, float x1, float y1, float x2, float y2) {
        float angle = findAngleRelative(x0, y0, x1, y1, x2, y2);
        if (angle > FastMath.PI) {
            angle -= FastMath.TWO_PI;
        }
        return angle;
    }

    /**
     * Return angle in range 0;2PI
     * @param x0
     * @param y0
     * @param x1
     * @param y1
     * @return
     */
    public static float findAngle(float x0, float y0, float x1, float y1) {
        float angle = findSignedAngle(x0, y0, x1, y1);
        if (angle < 0) {
            angle += FastMath.TWO_PI;
        }
        return angle;
    }

    public static float findAngleRelative(float x0, float y0, float x1, float y1, float x2, float y2) {
        float angle0to1 = findAngle(x0, y0, x1, y1);
        float angle0to2 = findAngle(x0, y0, x2, y2);
        if (angle0to2 < angle0to1) {
            angle0to2 += FastMath.TWO_PI;
        }
        float angle = angle0to2 - angle0to1;
        return angle;
    }

    public static Point midPoint(float x0, float y0, float x1, float y1) {
        return new Point((x0 + x1) / 2f, (y0 + y1) / 2f);
    }

    public static Point pointInDirection(float x0, float y0, float angle, float dist) {
        float xDist = dist * FastMath.cos(angle);
        float yDist = dist * FastMath.sin(angle);
        return new Point(x0 + xDist, y0 + yDist);
    }

    /**
     * returns dist from pt0 to line formed by pt1 and pt2
     * @param x0
     * @param y0
     * @param x1
     * @param y1
     * @param x2
     * @param y2
     * @return
     */
    public static float distToLineSq(float x0, float y0, float x1, float y1, float x2, float y2) {
        x2 -= x1;
        y2 -= y1;
        x0 -= x1;
        y0 -= y1;
        float dotProduct = x0 * x2 + y0 * y2;
        float projectionLengthSq = dotProduct * dotProduct / (x2 * x2 + y2 * y2);
        float distSq = x0 * x0 + y0 * y0 - projectionLengthSq;
        return distSq;
    }

    public static float distToLine(float x0, float y0, float x1, float y1, float x2, float y2) {
        float distSq = distToLineSq(x0, y0, x1, y1, x2, y2);
        return FastMath.sqrt(distSq);
    }

    public static float distToSegSq(float x0, float y0, float x1, float y1, float x2, float y2) {
        x2 -= x1;
        y2 -= y1;
        x0 -= x1;
        y0 -= y1;
        float dotProduct = x0 * x2 + y0 * y2;
        float projLengthSq = 0;
        if (dotProduct > 0) {
            // pt0 is in on the side of pt1 in direction of pt2
            // check if in also in direction of pt1 from relPos to pt2
            x0 = x2 - x0;
            y0 = y2 - y0;
            dotProduct = x0 * x2 + y0 * y2;
            if (dotProduct > 0) {
                projLengthSq = dotProduct * dotProduct / (x2 * x2 + y2 * y2);
            }
        }
        return x0 * x0 + y0 * y0 - projLengthSq;
    }

    public static float distToSeg(float x0, float y0, float x1, float y1, float x2, float y2) {
        return FastMath.sqrt(distToSegSq(x0, y0, x1, y1, x2, y2));
    }

    /**
     * segment from pt1 and pt2
     * @param x0
     * @param y0
     * @param x1
     * @param y1
     * @param x2
     * @param y2
     * @return
     */
    public static Point getClosestPointOnSegment(float x0, float y0, float x1, float y1, float x2, float y2) {
        float x2LessX1 = x2 - x1;
        float y2LessY1 = y2 - y1;
        float lNum = x2LessX1 * x2LessX1 + y2LessY1 * y2LessY1;
        float rNum = ((x0 - x1) * x2LessX1 + (y0 - y1) * y2LessY1) / lNum;
        if (rNum <= 0) {
            return new Point(x1, y1);
        } else if (rNum >= 1) {
            return new Point(x2, y2);
        } else {
            return new Point(x1 + rNum * x2LessX1, y1 + rNum * y2LessY1);
        }
    }

    public Rectangle rectangleUnion(Rectangle... rectangles) {
        float leftX = Float.MAX_VALUE;
        float rightX = -Float.MAX_VALUE;
        float botY = Float.MAX_VALUE;
        float topY = -Float.MAX_VALUE;
        for (Rectangle r : rectangles) {
            if (leftX > r.getX()) {
                leftX = r.getY();
            }
            if (rightX < r.getX() + r.getWidth()) {
                rightX = r.getX() + r.getWidth();
            }
            if (botY > r.getY()) {
                botY = r.getY();
            }
            if (topY < r.getY() + r.getHeight()) {
                topY = r.getY() + r.getHeight();
            }
        }
        return new Rectangle(leftX, botY, rightX - leftX, topY - botY);
    }

    public static com.vividsolutions.jts.geom.Polygon convertToJts(Polygon polygon) {
        final GeometryFactory geometryFactory = new GeometryFactory();
        final int nbPoints = polygon.getPoints().size();
        final Coordinate[] coords = new Coordinate[nbPoints + 1];
        for (int i = 0; i < nbPoints; i++) {
            Point p = polygon.getPoints().get(i);
            coords[i] = new Coordinate(p.getX(), p.getY());
        }
        coords[nbPoints] = (Coordinate) coords[0].clone();
        LinearRing ring = geometryFactory.createLinearRing(coords);
        com.vividsolutions.jts.geom.Polygon jtsPolygon;
        jtsPolygon = new com.vividsolutions.jts.geom.Polygon(ring, null, geometryFactory);
        return jtsPolygon;
    }

    /**
     * Returns the exterior polygon, discard holes
     * @param jtsPolygon
     * @return 
     */
    public static Polygon convertExteriorFromJts(com.vividsolutions.jts.geom.Polygon jtsPolygon) {
        LineString exteriorRing = jtsPolygon.getExteriorRing();
        return makePolygonFrom(exteriorRing);
    }

    /**
     * Returns the holes in the polygon
     * @param jtsPolygon
     * @return 
     */
    public static Set<Polygon> convertInteriorFromJts(com.vividsolutions.jts.geom.Polygon jtsPolygon) {
        Set<Polygon> polygons = new HashSet<Polygon>();
        for (int i = 0; i < jtsPolygon.getNumInteriorRing(); i++) {
            LineString ring = jtsPolygon.getInteriorRingN(i);
            Polygon pol = makePolygonFrom(ring);
            polygons.add(pol);
        }
        return polygons;
    }

    private static Polygon makePolygonFrom(LineString ring) {
        CoordinateSequence coordSequence = ring.getCoordinateSequence();
        List<Point> points = new ArrayList<Point>();
        Point prevPoint = null;
        for (int i = 0; i < coordSequence.size() - 1; i++) {
            Coordinate coord = coordSequence.getCoordinate(i);
            Point p = new Point((float) coord.x, (float) coord.y);
            if (prevPoint != null && prevPoint.posEquals(p)) {
                continue;
            }
            prevPoint = p.getCopy();
            points.add(p);
        }
        Polygon pol = new Polygon(points);
        return pol;
    }

    public static Polygon buffer(Polygon polygon, float bufferAmount, int linesInQuadrants) {
        if (bufferAmount == 0) {
            return polygon;
        }
        com.vividsolutions.jts.geom.Polygon jtsPolygon = convertToJts(polygon);
        Geometry geom = jtsPolygon.buffer(bufferAmount, linesInQuadrants);
        com.vividsolutions.jts.geom.Polygon bufferedPol = (com.vividsolutions.jts.geom.Polygon) geom;
        return convertExteriorFromJts(jtsPolygon);
    }

    public static Set<Polygon> merge(boolean discardHoles, Polygon... polygons) {
        com.vividsolutions.jts.geom.Polygon[] jtsPolygons = new com.vividsolutions.jts.geom.Polygon[polygons.length];
        Set<Polygon> mergedPolygons = new HashSet<Polygon>();
        for (int i = 0; i < polygons.length; i++) {
            Polygon p = polygons[i];
            jtsPolygons[i] = convertToJts(p);
        }
        GeometryFactory geometryFactory = new GeometryFactory();
        GeometryCollection geometryCollection = new GeometryCollection(jtsPolygons, geometryFactory);
        MultiPolygon multiPolygon = (MultiPolygon) geometryCollection.buffer(0);
        for (int i = 0; i < multiPolygon.getNumGeometries(); i++) {
            com.vividsolutions.jts.geom.Polygon jtsPolygon = (com.vividsolutions.jts.geom.Polygon) multiPolygon.getGeometryN(i);
            Polygon extPol = convertExteriorFromJts(jtsPolygon);
            mergedPolygons.add(extPol);
            if (!discardHoles) {
                for (int j = 0; j < jtsPolygon.getNumInteriorRing(); j++) {
                    Polygon intPol = makePolygonFrom(jtsPolygon.getInteriorRingN(j));
                    mergedPolygons.add(intPol);
                }
            }
        }
        return mergedPolygons;
    }
}
